package william.array;

/**
 * @author ZhangShenao
 * @date 2024/3/1
 * @description <a href="https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/description/">...</a>
 */
public class Leetcode167_两数之和2_输入有序数组 {
    /**
     * 采用对撞指针法,利用数组的有序性
     * 从左、右两端同时开始遍历数组,判断左、右两个元素的和是否=target
     * -如果和=target,直接返回当前两个索引
     * -如果和< target,则将左指针右移一位
     * -如果和 > target,则将右指针左移一位
     * <p>
     * 时间复杂度O(N) 只需要遍历数组一遍
     * 空间复杂度O(1)
     */
    public int[] twoSum(int[] numbers, int target) {
        //边界条件校验
        if (numbers == null || numbers.length < 2) {
            throw new IllegalArgumentException("invalid input!");
        }

        //采用对撞指针法,从左、右两个方向同时遍历数组,将结果夹出来
        int l = 0;
        int r = numbers.length - 1;
        while (l < r) { //因为不可以使用重复元素,因此l=r时不合法
            int sum = numbers[l] + numbers[r];
            if (sum == target) {    //加和=target,直接返回
                return new int[]{l + 1, r + 1};
            }
            if (sum < target) {  //加和<target,将左指针右移一位
                ++l;
            } else { //加和>target,将右指针左移一位
                --r;
            }
        }

        //无有效答案,直接抛异常
        throw new IllegalArgumentException("invalid input!");
    }
}
